/*
 * 0029. 交叉字符串
 * 给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
 * https://www.lintcode.com/problem/interleaving-string/description
 * 
 * 样例
 * 比如 s1 = "aabcc" s2 = "dbbca"
 * - 当 s3 = "aadbbcbcac"，返回  true.
 * - 当 s3 = "aadbbbaccc"， 返回 false.
 * 
 * 挑战
 * 要求时间复杂度为O(n^2)或者更好
 * 
 * 2018.06.28 @jeyming
 */
package interleaving_string_0029;

public class Interleaving_string_0029 {
	/**
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
    public static boolean isInterleave(String s1, String s2, String s3) {
        // write your code here
    	int cntA = 0;
    	int cntB = 0;
    	int cntC = 0;
    	while(cntC < s3.length()) {
    		boolean judge = false;
    		while((cntA < s1.length()) && (s1.charAt(cntA) == s3.charAt(cntC))) {
    			++cntA;
    			++cntC;
    			judge = true;
    			if((cntA < s1.length()) && (s1.charAt(cntA) != s3.charAt(cntC)) && (s2.charAt(cntB) == s1.charAt(cntA - 1))) {
    				cntA -= 1;
    				cntC -= 1;
    				break;
    			}
    		}
    		while((cntB < s2.length()) && (s2.charAt(cntB) == s3.charAt(cntC))) {
    			++cntB;
    			++cntC;
    			judge = true;
    			if((cntB < s2.length()) && (s2.charAt(cntB) != s3.charAt(cntC)) && (s1.charAt(cntA) == s2.charAt(cntB - 1))) {
    				cntB -= 1;
    				cntC -= 1;
    				break;
    			}
    		}
    		if(judge == false) {
    			return false;
    		}
    	}
    	return true;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String A = "sdfjas;dfjoisdufzjkndfasdkfja;sdfa;dfa;dfaskdjhfasdhjdfakhdgfkajdfasdjfgajksdfgaksdhfasdkbfjkdsfbajksdfhakjsdfbajkdfbakdjsfgaksdhgfjkdsghfkdsfgadsjfgkajsdgfkjasdfh";
		String B = "dfnakdjnfjkzghdufguweygfasjkdfgb2gf8asf7tgbgasjkdfgasodf7asdgfajksdfguayfgaogfsdkagfsdhfajksdvfbgkadsghfakdsfgasduyfgajsdkfgajkdghfaksdgfuyadgfasjkdvfjsdkvfakfgauyksgfajkefgjkdasgfdjksfgadjkghfajksdfgaskdjfgasjkdgfuyaegfasdjkfgajkdfygadjskfgjkadfg";
		String C = "sdfjas;dfjoisdfnakdjnfjkzghdufguwdufzjkeygfasjkdfgb2gf8asf7ndtgbgasjkdfgasodf7asdfgfajkasdksdfguayfgaogfsdkagfsfjadhfajksdvfbgkadsghfa;sdkdsfgasduyfgajsdkfgafajkdghfaksdgfuyadgfas;dfjkdvfjsdkvfakfgauyksa;dgfajkefgjkdasgfdjksffaskdjhfasdhjdfakhdgadjkghfajgfkajdfksdfgaskdjfgasjkdgfuasdjfgajksdfgaksdhfasdkbfjkdsfbajksdfyaegfasdjkfgajkdfygadjskfgjkadfghakjsdfbajkdfbakdjsfgaksdhgfjkdsghfkdsfgadsjfgkajsdgfkjasdfh";
		isInterleave(A,B,C);
	}

}
